#if 1
#include"RBTree.h"
#include<assert.h>

template<typename T>
RBTree<T>::RBTree()
{
	              // key, left, pa, right, color
	NIL = new RBNode<T>(0, nullptr, nullptr, nullptr, BLACK); 
	head = new RBNode<T>(0, NIL, NIL, NIL, RED);
	cursize = 0;
}

template<typename T>
RBTree<T>::~RBTree()
{
	delete head;
	delete NIL;
}

template<typename T>
void RBTree<T>::InOrder(RBNode<T>* root)
{
	if (root == NIL) return;
	else
	{
		InOrder(root->left);
		std::cout << root->key << " ";
		InOrder(root->right);
	}
}

template<typename T>
void RBTree<T>::NoRecInOrder()
{
	RBNode<T>* p = head->left;
	while (p != nullptr)
	{
		std::cout << p->key << " ";
		p = NextNode(p);
	}
	std::cout << std::endl;
}

template<typename T>
void RBTree<T>::MirrorNoRecInOrder()
{
	RBNode<T>* p = head->right;
	while (p != nullptr)
	{
		std::cout << p->key << " ";
		p = PreNode(p);
	}
	std::cout << std::endl;
}

template<typename T>
bool RBTree<T>::Insert(const T& key)
{
	if (head->parent == NIL)
	{
		head->parent = head->BuyNode(key, NIL, head, NIL, BLACK);
		assert(head->parent != nullptr);
		head->left = head->parent;
		head->right = head->parent;
	}
	else
	{
		RBNode<T>* p = head->parent;
		RBNode<T>* pa = p->parent;
		while (p != NIL && p->key != key)
		{
			pa = p;
			p = p->key < key ? p->right : p->left;
		}
		if (p != NIL && p->key == key) return false;
		p = p->BuyNode(key, NIL, pa, NIL, RED);
		assert(p != nullptr);
		key > pa->key ? pa->right = p : pa->left = p;
		if (head->left->key > key)
		{
			head->left = p;
		}
		if (head->right->key < key)
		{
			head->right = p;
		}
		AdjustTree(p);
	}
	++cursize;
	return true;
}

template<typename T>
bool RBTree<T>::Delete(const T& key)
{
    
}

template<typename T>
RBNode<T>* RBTree<T>::FindValue(RBNode<T>* root, const T& key)
{
	if (root == NIL) return nullptr;
	else if(key == root->key) return root;
	else if (key < root->key) return  FindValue(root->left, key);
	else return FindValue(root->right, key);
}

template<typename T>
RBNode<T>* RBTree<T>::NoRecFindValue(const T& key)
{
	if (IsEmpty()) return nullptr;
	RBNode<T>* p = head->parent;
	while (p != NIL && key != p->key)
	{
		p = key > p->key ? p->right : p->left;
	}
	if (p == NIL) p = nullptr;
	return p;
}

template<typename T>
int RBTree<T>::GetSize()
{
	return cursize;
}

template<typename T>
RBNode<T>* RBTree<T>::GetHead()
{
	return head;
}

template<typename T>
bool RBTree<T>::IsEmpty()
{
	return cursize == 0;
}

template<typename T>
bool RBTree<T>::Is_BSTTree(RBNode<T>* root)
{
	if (root == NIL) return true;
	RBNode<T>* pre = head->left;
	RBNode<T>* p = NextNode(pre);
	while (p != nullptr)
	{
		if (pre->key > p->key) return false;
		pre = p;
		p = NextNode(p);
	}
	return true;
}

template<typename T>
bool RBTree<T>::Is_RBTree(RBNode<T>* root)
{
	return true;
}

template<typename T>
RBNode<T>* RBTree<T>::NextNode(RBNode<T>* node)
{
	if (node == NIL) return nullptr;
	if (node->right != NIL)
	{
		node = node->right;
		while (node->left != NIL) node = node->left;
		return node;
	}
	while (node->parent != head)
	{
		RBNode<T>* pa = node->parent;
		if (pa->left == node) return pa;
		node = pa;
	}
	return nullptr;
}

template<typename T>
RBNode<T>* RBTree<T>::PreNode(RBNode<T>* node)
{
	if (node == NIL) return nullptr;
	if (node->left != NIL)
	{
		node = node->left;
		while (node->right != NIL) node = node->right;
		return node;
	}
	while (node->parent != head)
	{
		RBNode<T>* pa = node->parent;
		if (pa->right == node) return pa;
		node = pa;
	}
	return nullptr;
}

template<typename T>
void RBTree<T>::RotateLeft(RBNode<T>* node)
{
	RBNode<T>* pa = node->parent;
	RBNode<T>* pNewRoot = node->right;

	node->right = pNewRoot->left;
	if (pNewRoot->left != NIL)
	{
		pNewRoot->left->parent = node;
	}

	pNewRoot->left = node;
	node->parent = pNewRoot;

	if (pa == head)
	{
		head->parent = pNewRoot;
		pNewRoot->parent = head;
	}
	else
	{
		node->key > pa->key ? pa->right = pNewRoot : pa->left = pNewRoot;
		pNewRoot->parent = pa;
	}
}

template<typename T>
void RBTree<T>::RotateRight(RBNode<T>* node)
{
	RBNode<T>* pa = node->parent;
	RBNode<T>* pNewRoot = node->left;

	node->left = pNewRoot->right;
	if (pNewRoot->right != NIL)
	{
		pNewRoot->right->parent = node;
	}

	pNewRoot->right = node;
	node->parent = pNewRoot;

	if (pa == head)
	{
		head->parent = pNewRoot;
		pNewRoot->parent = head;
	}
	else
	{
		node->key > pa->key ? pa->right = pNewRoot : pa->left = pNewRoot;
		pNewRoot->parent = pa;
	}
}

template<typename T>
void RBTree<T>::AdjustTree(RBNode<T>* node)
{
	RBNode<T>* _X = node;
	RBNode<T>* _Y = nullptr;
	for (; _X != head->parent && _X->parent->color == RED;)
	{
		if (_X->parent == _X->parent->parent->right)
		{
			_Y = _X->parent->parent->left;
			if (_Y->color == RED)
			{
				_Y->color = BLACK;
				_X->parent->color = BLACK;
				_X->parent->parent->color = RED;
				_X = _X->parent->parent;
			}
			else
			{
				if (_X == _X->parent->left)
				{
					_X = _X->parent;
					RotateRight(_X);
				}
				_X->parent->color = BLACK;
				_X->parent->parent->color = RED;
				RotateLeft(_X->parent->parent);
			}
		}
		else
		{
			_Y = _X->parent->parent->right;
			if (_Y->color == RED)
			{
				_Y->color = BLACK;
				_X->parent->color = BLACK;
				_X->parent->parent->color = RED;
				_X = _X->parent->parent;
			}
			else
			{
				if (_X == _X->parent->right)
				{
					_X = _X->parent;
					RotateLeft(_X);
				}
				_X->parent->color = BLACK;
				_X->parent->parent->color = RED;
				RotateRight(_X->parent->parent);
			}
		}
	}
	head->parent->color = BLACK;
}
#endif